package com.zhledu.parallel.lanqiao;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

/*宽搜的思路
1，抽象状态和level
2, 利用queue队列
3,判重避免死循环 Set<String> allState=new HashSet<String>()


*/
public class Frog {
    //将target和start作为全局变量
    private static StringBuilder start;
    private static StringBuilder target;
    static Set<String> allState=new HashSet<String>();//帮助去重
    //1.封装一个持有状态和层次的类
    private static class StateAndLevel{
        StringBuilder state;
        int level;
        int pos;//(空杯子)的位置
        //构造器
        public StateAndLevel(StringBuilder state,int level,int pos) {
            this.state=state;
            this.level=level;
            this.pos=pos;
        }
    }
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        start = new StringBuilder(sc.nextLine());
        target = new StringBuilder(sc.nextLine());
        bfs();//宽搜
    }
    private static void bfs() {
        //将初始化加入到队列中
        Queue<StateAndLevel> q=new LinkedList<StateAndLevel>();//宽搜要用队列（Queue），用LinkedList来实现
        q.add(new StateAndLevel(start,0,start.indexOf("*")));//加入最初始的那种状态。
        allState.add(start.toString());//用于判重
        //3.不停弹出队首，一步演化成相邻状态，加入队列中（判重）。
        while (!q.isEmpty()) {
            //如果不为空，弹出队首。
            StateAndLevel front=q.poll();//弹出头部。
            StringBuilder state =front.state;
            int level=front.level;
            //和目标值做比对,StringBulider比的是地址，要按内容比就toString()
            if (state.toString().equals(target.toString())) {
                System.out.println(level);
                break;
            }
            int pos=front.pos;
            //可以演化出若干的相邻状态。
            for (int i = -3; i<=3; i++) {//代表*的位置，范围是满足题目要求青蛙可以跳的范围，
                if (i==0)continue;
                if (pos+i>=0 && pos+i<state.length()) {
                    StringBuilder new_state=new StringBuilder(state);
                    swap(new_state,pos,pos+i);//交换位置达到新事的状态。
                    if (!allState.contains(new_state.toString())) {//判重成功
                        q.add(new StateAndLevel(new_state, level+1, pos+i));//放入队列
                        allState.add(new_state.toString());
                    }
                }
            }
        }
    }
    private static void swap(StringBuilder a, int i, int j) {
        char t=a.charAt(i);
        a.setCharAt(i, a.charAt(j));
        a.setCharAt(j,t);
    }

}
